package com.jxb.first;

/**
 * 链表中倒数第k个节点
 */
public class KthFromTail_Offer22 {

    public static void main(String[] args) {
        //n-k+1
//        System.out.println(8-2+1);
        ListNode listNode1 = new ListNode();
        listNode1.val = 1;
        ListNode listNode2 = new ListNode();
        listNode2.val = 2;
        ListNode listNode3 = new ListNode();
        listNode3.val = 3;
        ListNode listNode4 = new ListNode();
        listNode4.val = 4;
        ListNode listNode5 = new ListNode();
        listNode5.val = 5;
//        ListNode listNode6 = new ListNode();
//        listNode6.val = 6;
//        listNode5.next = listNode6;
        listNode4.next = listNode5;
        listNode3.next = listNode4;
        listNode2.next = listNode3;
        listNode1.next = listNode2;
        ListNode listNode = kthNodeFromEnd1(listNode1, 3);
        System.out.println(listNode);
    }

    //通过链表长度计算出节点位置，然后遍历，获取节点内容-时间复杂度O(n)，空间复杂度O(1)
    public static ListNode kthNodeFromEnd(ListNode head , int kthNode){
        ListNode temp = head;
        int length = 0;
        while (temp != null) {
            length++;
            temp = temp.next;
        }
        //计算元素位置
        int offset = length - kthNode + 1;
        temp = head;
        int index = 1;
        while (temp != null) {
            if (offset == index) {
                return temp;
            }
            temp = temp.next;
            index ++;
        }
        return null;
    }

    //双指针（快指针进行k次移动后，慢指针再移动，当慢指针移动到最后一个节点，慢指针指定的节点就是需要的节点），时间复杂度为O(n)，空间复杂度为O(1)
    public static ListNode kthNodeFromEnd1(ListNode head , int k){
        ListNode fastP = head;
        ListNode slowP = head;
        int index = 0;
        while (fastP != null) {
            fastP = fastP.next;
            if (index >= k) {
                slowP = slowP.next;
            }
            index ++;
        }
        return slowP;
    }

}
